﻿//search for best move
namespace FSharpChess
open System

type search_current_t =
    {
        mutable psn:Posn;
        mutable timer:TimeSpan;
        max_depth:int;
        mutable node_nb:uint64;
        time:double;
        speed:double;
        cpu:double;
    }
type search_info_t =
    {
        can_stop:bool;
        stop:bool;
        mutable check_nb:int;
        check_inc:int;
        last_time:double;
    }
    
module Search =
    let SearchCurrent =
        {
            psn=Posn.blank;
            timer=new TimeSpan();
            max_depth=0;
            node_nb=0UL;
            time=0.0;
            speed=0.0;
            cpu=0.0;
        }
    let SearchInfo =
        {
            can_stop=false;
            stop=false;
            check_nb=0;
            check_inc=0;
            last_time=0.0;
        }
    






























    let Move_Blank = Move.blank
    let mutable MaximumSearchDepth = 10
    let MinimumSearchDepth = 1
    let MIN_SCORE = System.Int32.MinValue + 1
    let MAX_SCORE = System.Int32.MaxValue
    let gmanals = 
        let Anal_Blank = Anal.create(Posn.blank,0,0)
        Anals.create (Anal_Blank,new ResizeArray<Move>(),1,(if MaximumSearchDepth = 0 then 32 else MaximumSearchDepth),ref false)
    let rec AlphaBeta(player,ply,depth,alpha,beta,moveAnalysed:Move,movesPV_Parent:ResizeArray<Move>,intTotalExtensions,an) =
        if gmanals.getimm()||(not (moveAnalysed.isBlank()) && moveAnalysed.IsThreeMoveRepetition) then
            (movesPV_Parent,beta)
        else
            let checks = Move_gen.do_checks an.Psn
            let blnIsInCheck = (List.length checks)>0
            an.PosSearched <- an.PosSearched+1
            let vlu,pbmv = Bms.ProbeHash(ply, alpha, beta, player.prIsWhite,Ref.FiftyMoveDrawBase,an.Psn)
            if (vlu <> System.Int32.MinValue) then
                let movesPVout = new ResizeArray<Move>()
                movesPVout.Add(pbmv)
                // High values of "valu" indicate that a checkmate has been found
                if (vlu > 1000000 || vlu < -1000000) && (gmanals.MaxSearchDepth - depth > 0) then
                    (movesPVout,vlu / (gmanals.MaxSearchDepth - depth))
                else
                    (movesPVout,vlu)
            else
                // Depth <=0 means we're into Quiescence searching
                let intScoreAtEntry = if (depth <= 0) then Eval.Score(player,an.Psn,blnIsInCheck,checks) else 0 
                let vlu =
                    if (depth <= 0) then
                        let vlu1 = intScoreAtEntry
                        if (vlu1 > 1000000 || vlu1 < -1000000) then
                            vlu1 / (gmanals.MaxSearchDepth - depth)
                        else
                            vlu1
                    else
                        System.Int32.MinValue
                    // Allow a deeper ply of search if a piece was captured or if a pawn was promoted, 
                if (depth <= 0) && (not( moveAnalysed.pieceCaptured <> -1 || moveAnalysed.mvName = PawnPromotionQueen)) then
                        (movesPV_Parent,vlu)
                else
                    // Adaptive Null-move forward pruning
                    let R = (if depth > 6 then 3 else 2)
                    let (movesPV,vlu1) =
                        if (depth > (R + 1) && not (moveAnalysed.isBlank()) && moveAnalysed.mvName <> NullMove && Funcs2.Stage(an.Psn) <> End && not blnIsInCheck) then
                            let moveNull = an.Psn.CreateMove(NullMove, -1, -1, -1, -1, 0)
                            AlphaBeta(Attack.OtherPlayer(player),ply - 1,depth - R - 1,-beta, -beta + 1,moveNull,(new ResizeArray<Move>()),intTotalExtensions,an)
                        else
                            (new ResizeArray<Move>(),-vlu)
                    if (-vlu1 >= beta) then
                        (movesPV_Parent,beta)
                    else
                        let gntyp = if blnIsInCheck then GenEvasions elif depth > 0 then GenAll else GenCaptures
                        let movesPossible = Sort.mvsPossF player an.Psn gntyp ply checks
                        let SetExt ma mpr =
                            let m_aintMargin = [|0;   0;   0; 5000; 5000; 7000; 7000; 9000;9000;15000;15000;15000;15000;15000;15000;15000;15000;15000|]
                            // Futility Pruning
                            // Standard Futility Pruning
//                            let scrn() = Eval.Score(player,an.Psn,blnIsInCheck)
//                            if not blnIsInCheck && depth=2 && mpr.pieceCaptured = -1 && (scrn() + 3000 <= ma) then
//                                -1
//                            // Extended Futility Pruning
//                            elif not blnIsInCheck && depth=3 && mpr.pieceCaptured = -1 && (scrn() + 5000 <= ma) then
//                                -1
//                            // Reductions
//                            elif depth > 2 && not blnIsInCheck && mpr.pieceCaptured = -1 && (ma > scrn() + m_aintMargin.[depth]) then
//                                -1
//                            // Search Extensions
//                            elif (movesPossible.Mvs.Count = 1) then
//                            if (movesPossible.Mvs.Count = 1) then
//                                // Single Response
//                                1
//                            elif blnIsInCheck then
                            if blnIsInCheck then
                                // Check evasion
                                1
                            elif (not (moveAnalysed.isBlank()) && moveAnalysed.pieceCaptured <> -1 && mpr.pieceCaptured <> -1 && Eval.Value(moveAnalysed.pieceCaptured,an.Psn) = Eval.Value(mpr.pieceCaptured,an.Psn)&& moveAnalysed.To = mpr.To) then
                                // Recapture piece of same basic value (on the same square)
                                1
                            elif (an.Psn.Pcs.[mpr.mvPiece].Name = enmName.Pawn && (an.Psn.Pcs.[mpr.mvPiece].pcIsWhite && Ref.ri.[mpr.To] = 6 || not an.Psn.Pcs.[mpr.mvPiece].pcIsWhite && Ref.ri.[mpr.To] = 1)) then
                                // enmName.Pawn push to 7th rank
                                1
                            else
                                0
                        let AssignKiller mb =
                            // 15Mar06 Nimzo Don't include captures as killer moves
                            if ((mb.pieceCaptured = -1) && (moveAnalysed.isBlank() || (moveAnalysed.mvName <> NullMove))) then
                                let moveKillerA = Kms.arrA.[ply+32]
                                if moveKillerA.isBlank() then
                                    Kms.assignA(ply, mb)
                                elif (Sort.MovesMatch mb moveKillerA) then
                                    let mka = {moveKillerA with Score=mb.Score}
                                    Kms.assignA(ply, mka)
                                else
                                    let moveKillerB = Kms.arrB.[ply+32]
                                    if moveKillerB.isBlank() then
                                        Kms.assignB(ply, mb)
                                    elif (Sort.MovesMatch mb moveKillerB) then
                                        let mkb = {moveKillerB with Score=mb.Score}
                                        Kms.assignB(ply,mkb)
                                    elif (mb.Score > moveKillerB.Score) then
                                        if (mb.Score > moveKillerA.Score) then
                                            Kms.assignB(ply, moveKillerA)
                                            Kms.assignA(ply, mb)
                                        else
                                            Kms.assignB(ply, mb)
                            // End Nimzo code
                        let rec GetBest i ma ht (mb:Move) bl il (mpv:ResizeArray<Move>) =
                            if Sort.mvspFin player an.Psn checks ply movesPossible i then
                                if (il = 0) then
                                    // Record best move
                                    let scr1 = Eval.Score(player,an.Psn,blnIsInCheck,checks)
                                    if not (mb.isBlank()) then
                                        Bms.RecordHash(ply, scr1, ht, mb, player.prIsWhite,an.Psn)
                                    (mpv,scr1)
                                else
                                    if not (mb.isBlank()) then
                                        Bms.RecordHash(ply, ma, ht, mb, player.prIsWhite,an.Psn)
                                    (mpv,ma)
                            else
                                let move = movesPossible.Mvs.[i]
                                if not (Move_do.DoMoveOK(move,an.Psn)) then 
                                    GetBest (i+1) ma ht mb bl il mpv
                                else
                                    let intExtension = if gntyp<>GenCaptures then SetExt ma move else 0
                                    let mpv1,vlu1 =
                                        if bl then
                                            let (mpv3,tmp3) = AlphaBeta(Attack.OtherPlayer(player),ply - 1,(depth + intExtension) - 1,-ma - 1,-ma,move,movesPV,intTotalExtensions + intExtension,an)
                                            if ((-tmp3 > ma) && (-tmp3 < beta)) then //fail
                                                let (mpv2,tmp2) = AlphaBeta(Attack.OtherPlayer(player),ply - 1,(depth + intExtension) - 1,-beta, -ma,move,movesPV,intTotalExtensions + intExtension,an)
                                                mpv2,-tmp2
                                            else
                                                mpv3,-tmp3
                                        else
                                            let (mpv2,tmp2) = AlphaBeta(Attack.OtherPlayer(player),ply - 1,(depth + intExtension) - 1,-beta,-ma,move,movesPV,intTotalExtensions + intExtension,an)
                                            mpv2,-tmp2
                                    let vlu =
                                        if gntyp=GenCaptures && vlu1 < intScoreAtEntry then
                                            // pr code is executed mostly in quiescence when not all moves are tried (maybe just captures)
                                            // and the best score we've got is worse than the score we had before we considered any moves
                                            // then revert to that score, because we dont want the computer to think that it HAS to make a capture
                                            intScoreAtEntry
                                        else
                                            vlu1
                                    movesPossible.Mvs.[i] <- {move with Score=vlu}
                                    let movepr = {move with Score=vlu}
                                    Move_do.Undo(movepr,an.Psn)
                                    if (vlu >= beta) then
                                        if (move.Score < 20000) then AssignKiller movepr
                                        if not (mb.isBlank()) then
                                            Bms.RecordHash(ply, beta, Beta, movepr, player.prIsWhite,an.Psn)
                                        (mpv,beta)
                                    else
                                        let mpvo =
                                            if (vlu > ma) then
                                                // Collect the Prinicipal Variation
                                                let tmp = new ResizeArray<Move>()
                                                tmp.Add(movepr)
                                                for i = 0 to mpv1.Count-1 do
                                                    let moveCopy = mpv1.[i]
                                                    tmp.Add(moveCopy)
                                                tmp
                                            else
                                                mpv
                                        if (Funcs2.IsThinking(player) && not Funcs2.IsInAnalyseMode && not Funcs2.IsPondering && an.SearchDepth > MinimumSearchDepth && (DateTime.Now - player.Clock.TurnStartTime) > player.ThinkingTimeMaxAllowed) then
                                            gmanals.setimm(true)
                                        if (vlu > ma) then
                                            GetBest (i+1) vlu Exact movepr true (il+1) mpvo
                                        elif mb.isBlank() then
                                            GetBest (i+1) ma ht movepr bl (il+1) mpvo
                                        else
                                            GetBest (i+1) ma ht mb bl (il+1) mpvo
                        GetBest 0 alpha Alpha Move_Blank false 0 movesPV_Parent
    let Aspirate(player,depth,lastS) =
        //just do not aspirate
        let an=gmanals.Anl
        AlphaBeta(player,an.SearchDepth,an.SearchDepth,MIN_SCORE,MAX_SCORE,Move_Blank,new ResizeArray<Move>(),0,an)
